package week_07;

import org.junit.Test;
import org.w3c.dom.Node;

import java.util.Iterator;

public class Stack<T> implements Iterable<T> {
    private Node head;
    private int N;


    protected class Node {
        public T item;
        public Node next;

        public Node(T item, Node next) {
            this.item = item;
            this.next = next;
        }
    }

    /**
     * 初始化头节点
     */
    public Stack() {
        this.head = new Node(null, null);
        this.N = 0;
    }

    /**
     * 判断当前栈里面受否为空
     *
     * @return
     */
    public boolean isEmpty() {
        return N == 0;
    }

    /**
     * 获取栈中元素的个数
     *
     * @return
     */
    public int size() {
        return N;
    }

    /**
     * 元素压栈
     *
     * @param t
     */
    public void push(T t) {
        Node oldFirst = head.next;
        Node newNode = new Node(t, null);
        head.next = newNode;
        newNode.next = oldFirst;
        N++;
    }

    /**
     * 元素出栈
     *
     * @return
     */
    public T pop() {
        Node oldFirst = head.next;
        if (oldFirst == null) {
            return null;
        }
        head.next = oldFirst.next;
        N--;
        return oldFirst.item;
    }

    /**
     * 判断str中的左右括号是否匹配
     * 括号匹配
     *
     * @param str 括号组成的字符串
     * @return 如果匹配返回true，不匹配返回false
     */
    public boolean isMatch(String str) {
//        1.创建栈对象，用来存储左括号
        Stack<String> chars = new Stack<>();
//        2.从左往右遍历字符串
        for (int i = 0; i < str.length(); i++) {
            String curChar = str.charAt(i) + "";
//        3.判断当前字符是否尾左括号,如果是则把字符放入栈中
            if (curChar.equals("(")) {
                chars.push(curChar);
            } else if (curChar.equals(")")) {
// 4.继续判断当前字符是否是有括号，如果有从栈中弹出左括号，并判断弹出的结果是否问null，如果为null证明没有匹配的左括号，不过部位null则有匹配的左括号
                String pop = chars.pop();
                if (pop == null) {
                    return false;
                }
            } else if (curChar.equals("[")) {
                chars.push(curChar);
            } else if (curChar.equals("]")) {
                String pop = chars.pop();
                if (pop == null) {
                    return false;
                }
            } else if (curChar.equals("{")) {
                chars.push(curChar);
            } else if (curChar.equals("}")) {
                String pop = chars.pop();
                if (pop == null) {
                    return false;
                }
            }
        }
//        5.判断栈中还有没有剩余的左括号，如果有证明括号不匹配
        if (chars.size() == 0) {
            return true;
        } else {
            return false;
        }
    }

    /**
     * 逆波兰表达式的实现
     *
     * @param notation 传如的逆波兰表达式的字符串
     * @return 计算结果
     */
    public int polishExpression(String[] notation) {
//1.定义一个栈，用来存储操作数
        Stack<Integer> operands = new Stack<>();

//2.从左往有遍历逆波兰表达式，得到每一个元素
        for (int i = 0; i < notation.length; i++) {
            String cur = notation[i];
//3.判断当前元素是运算符还是操作数
            Integer o1;
            Integer o2;
            Integer result;
            switch (cur) {
                case "+":
//4.运算符，需要从栈中弹出两个数完成运算，然后把运算结果压入到栈中
                    o1 = operands.pop();
                    o2 = operands.pop();
                    result = o2 + o1;
                    operands.push(result);
                    break;
                case "-":
                    o1 = operands.pop();
                    o2 = operands.pop();
                    result = o2 - o1;
                    operands.push(result);

                    break;
                case "*":
                    o1 = operands.pop();
                    o2 = operands.pop();
                    result = o2 * o1;
                    operands.push(result);
                    break;
                case "/":
                    o1 = operands.pop();
                    o2 = operands.pop();
                    result = o2 / o1;
                    operands.push(result);
                    break;
                default:
                    operands.push(Integer.valueOf(cur));
                    break;
            }
        }


//        5.如果是操作数就把操作数放入栈中
        //        6.得到栈中最后一个元素就是逆波兰表达式的结果
        return operands.pop();
    }

    public boolean variantJudge(String str) {
//        1.创建一个栈用来存储数据
        Stack<String> stack = new Stack<>();
//        2.从左往右遍历字符串
        for (int i = 0; i < str.length(); i++) {
            String cur = str.charAt(i) + "";
//        3.判断回文字符串为奇数还是偶数，奇数就可以不用管中间的那个字符，偶数就要考虑
            if (str.length() % 2 == 0) {
                if (i < str.length() / 2) {
                    stack.push(cur);
                } else if (i >= str.length() / 2) {
                    String pop = stack.pop();
//        4.判断如果字符串左右对称就是回文字符串，否则就不是
//                如果弹出的字符与当前字符相对应
                    if (!cur.equals(pop)) {
                        return false;
                    }
                }
            } else {
                if (i < str.length() / 2) {
                    stack.push(cur);
                } else if (i > str.length() / 2) {
                    String pop = stack.pop();
                    if (!cur.equals(pop)) {
                        return false;
                    }
                }
            }

        }
        return stack.size() == 0;


    }

    public void fullArrangementCheck(String[] str ){
        for (int i = 0; i < str.length; i++) {
            for (int j=0;j<str[i].length();j++){
                if (j<str[i].length()-1){
                    if ("b".equals(String.valueOf(str[i].charAt(j)))&&"a".equals(String.valueOf(str[i].charAt(j+1)))){
                        push((T) str[i]);
                    }else if ("c".equals(String.valueOf(str[i].charAt(j)))&&"b".equals(String.valueOf(str[i].charAt(j+1)))){
                        push((T) str[i]);
                    }
                    else if ("d".equals(String.valueOf(str[i].charAt(j)))&&"c".equals(String.valueOf(str[i].charAt(j+1)))){
                        push((T) str[i]);
                    }
                    else if ("e".equals(String.valueOf(str[i].charAt(j)))&&"d".equals(String.valueOf(str[i].charAt(j+1)))){
                        push((T) str[i]);
                    }
                }
            }
        }


    }
    @Override
    public Iterator<T> iterator() {
        return new SIterator();
    }

    public class SIterator implements Iterator {
        private Node n;

        public SIterator() {
            this.n = head;
        }

        @Override
        public boolean hasNext() {
            return n.next != null;
        }

        @Override
        public Object next() {
            n = n.next;
            return n.item;
        }
    }


}
